Compilers convert a source program that is usually written in a high level language into low level object code, which typically consists of a sequence of machine instructions or assembly language. The constructs in the source program are converted into a sequence of assembly language instructions. To achieve the highest possible efficiency of operation, it is essential to know exactly how much time the program takes to execute. In order to concentrate on those parts of the program that need improvements in efficiency, the length of time that the program takes to execute, and other statistics about the program execution, at the function level, at the loop level, and at the basic block level must be determined. Specialized programs have been used to conduct measurements of the required program performance characteristics necessary to acquire such data.
One such program is the instrumentor either static or dynamic. Instrumentors conduct specific tasks within binary files such as assessing instruction types and adding program code where appropriate. If, for example, a desired point of code insertion is identified, the instrumentor will add program instructions which precede this point so as to monitor the operation of the main program at this point. The instrumentor then rewrites the binary file in a manner such that when the modified program is finally executed, both the original binary instructions and the instrumenting instructions will execute, thus producing output resulting from both the original binary program code, as well as from the instrumenting code.
A problem faced by instrumenting tools after deciding that instrumenting code is to be added to a program, is that of finding temporary storage space in which to store data. Using memory would avoid interference with the main program, but slows execution. It is therefore necessary to use registers, and as many of them as possible. The problem here lies in determining which registers can be used without interfering with operations of the main program. Four principal techniques have been used in the prior art to address this problem.
The first of these prior art techniques involves deciding upon a set of registers for use by the instrumenting program. Then, to preclude interference with the main program by the instrumenting program, the values of the selected registers are saved to memory. The instrumentor performs whatever operations are required for its purposes, employing the selected registers, and then retrieves the original values of the selected registers from memory.
One advantage of this approach is its safety. Because the data originally present in the selected registers is saved to memory and then retrieved after instrumentor operations are complete, the instrumentor does not harm the original data. A further advantage is that during instrumentation, time is saved because the instrumentor does not check the operation of the main program with regard to the selected registers, before saving their contents to memory.
The principal disadvantage of this first approach is that movement of data between the registers and memory locations is slow, and in this case, the contents of all selected registers is saved to memory regardless of whether the data in these registers is useful to the main program or not. As such, there is likely some wasteful data transfer to and from memory using this technique. This movement of useless data to and from memory from the registers is computationally expensive and is a major drawback of this first technique.
The second approach seeks to avoid the time consuming movement of register contents to and from memory by determining which registers contain data to be subsequently accessed by the main program and which do not. This involves a process of global analysis which by itself is quite time consuming. The second technique operates as follows.
At every point in the main program where the instrumentor decides to place instrumenting code, the registers available for instrumentation have to be identified. Arcs or lines are drawn between the points in the program where data in particular registers is stored and accessed. If the point in the program where the instrumentor seeks to place code is in between the points where data is stored in a register and data from this register is accessed, the register is deemed unavailable for instrumentation. Once a sufficient number of available registers is identified, the instrumentor uses these identified registers for the instrumenting code needed at that point in the program. This analysis must be performed at every point where instrumentation code is to be inserted.
The advantages of this approach are that it is safe and precise. It is also quick to run in the execution phase because the data traffic between the registers and memory mentioned in the first technique is absent here. The main disadvantage is that the register availability determinations made during the instrumenting phase are time consuming. Here, there is slow instrumentation and rapid execution which is the opposite of the situation in the first technique.
A distinguishing characteristic of the first two approaches is that they are both applicable to situations where the designer of the instrumenting program has no control over the design of the original or main program, and no provision is made in the main program to provide for the instrumentation program. The following two techniques address situations where there is some cooperation between the design of the original program and the instrumenting program.
The third technique involves cooperation between the development of the original compiler program and the instrumentor program in the form of expressly reserving certain registers for use by the instrumentor program when designing the original compiler program. Using this approach, the instrumentor program has the advantages associated with both of the first two techniques discussed above, with none of the disadvantages. Since the registers are set aside in advance, the instrumentor program is not burdened with the need to check for availability of the registers. The arrangement is such that the compiler program will not have used these registers and will therefore not have any data in them to be destroyed. Further, assuming that a sufficient number of registers has been set aside, the instrumentor program will not have to transfer data between the registers and memory, thereby obviating the need for this time consuming data transfer process.
One disadvantage associated with the third technique is that the reservation of registers for the instrumentor program reduces the number of registers available for the compiler program. The compiler program, which is written in anticipation of the need for registers by an instrumentor program, will likely have to move data between registers and memory more often than it would otherwise because of the reduced number of available registers. The compiler program is therefore likely to run more slowly. Further, many compiler programs written in anticipation of the use of instrumenting programs will never in fact be instrumented. Therefore, it is a further disadvantage that the burden imposed on the compiler program may be uncompensated by a benefit to an instrumenting program.
A fourth technique uses a looser form of cooperation between compiler and instrumentor. The compiler program is written taking full advantage of the registers provided by the processor, thus permitting optimum execution efficiency. The compiler program however, leaves information embedded in the program, at the bottom of each basic block of code for the instrumentor program to read, indicating which registers are available for use by the instrumentor program in that block. Compilers typically have to acquire such information anyway, so presenting such information for reading by the instrumentor program imposes little additional burden on the compiler program.
If, for a particular block of code, no registers are available, the instrumentor program reverts to the first technique discussed above. It preserves the contents of a selected number of registers in memory and proceeds to use those registers for instrumenting operations within that block Although this process is computationally expensive, unlike with the first technique, it is used only when no registers are available, and thus does not needlessly save useless data to memory.
The principal disadvantage of this fourth technique is that the embedded register availability information referred to above occupy substantial disk space. In a typical compiler program, supplying the required information about available registers could increase the size of the compiler program by half This tends to inconvenience customers by occupying more of their hard disk space, and can slow down the operation of an overall system by requiring more transfer of data between disk and memory.
Therefore, there is a need in the art for an instrumenting program which will execute rapidly, permit the original compiler program execute rapidly, and protect all data needed by the original program code. There is a further need in the art for an instrumenting program which will not cause the compiler to require additional memory space. There is a still farther need in the art for an instrumenting scheme which will not require advance cooperation in the design of the compiler program and the instrumenting program.